# https://leetcode-cn.com/problems/integer-break/
# 343. 整数拆分

# class Solution:
#     def integerBreak(self, n: int) -> int:
#         dp = [0] * (n+1)
#         res = 0
#         for i in range(2, n+1):
#             if (n % i == 0):
#                 dp[i] = (n//i) ** i
#                 res = max(dp[i], res)
#             else:
#                 temp = n // i
#                 dp[i] = (temp)**(i-1) * (n-temp*(i-1))
#                 res = max(dp[i], res)
#         print(res)
#         print(dp)
#         return res


class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[2] = 1
        for i in range(3, n+1): 
            for j in range(1, i-1):
                dp[i] = max(dp[i], max(j * (i-j), dp[i-j] * j))
        print(dp)
        return dp[n]


a = Solution()
a.integerBreak(8)
